package tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class BinaryTreePostorderTraversal145 {
//todo
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        LinkedList<Integer> result = new LinkedList<>();
        while (root != null || stack.size() != 0) {
            while (root != null) {
                result.addFirst(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return result;

    }

//        public List<Integer> postorderTraversal(TreeNode root) {
//        List<Integer> result = new ArrayList<>();
//        if(root==null){
//            return result;
//        }
//        postorderTraversal(root,result);
//        return result;
//    }
//
//    private void postorderTraversal(TreeNode root, List<Integer> result) {
//        if(root == null){
//            return;
//        }
//        postorderTraversal(root.left,result);
//        postorderTraversal(root.right,result);
//        result.add(root.val);
//    }

}
